#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int maxn = 1e5+5;
int key[maxn],Next[maxn];
map<int,int> m;
vector<int> v,v1,v2;

signed main()
{
    int begin,n;
    cin>>begin>>n;
    for(int i=0;i<n;i++){
        int ad;
        cin>>ad>>key[ad]>>Next[ad];
    }
    while(begin!=-1){
        v.push_back(begin);
        begin = Next[begin];
    }
    for(int i=0;i<v.size();i++){
        if(m.find(abs(key[v[i]]))==m.end()){
            v1.push_back(v[i]);
            m[abs(key[v[i]])] = 1;
        }
        else{
            v2.push_back(v[i]);
        }
    }
    if(v1.size()){
        printf("%05d %d ",v1[0],key[v1[0]]);
        for(int i=1;i<v1.size()-1;i++){
            printf("%05d\n%05d %d ",v1[i],v1[i],key[v1[i]]);
        }
        if(v1.size()>1)    printf("%05d\n%05d %d -1\n",v1[v1.size()-1],v1[v1.size()-1],key[v1[v1.size()-1]]);
        else    cout<<"-1";
    }
    if(v2.size()){
        printf("%05d %d ",v2[0],key[v2[0]]);
        for(int i=1;i<v2.size()-1;i++){
            printf("%05d\n%05d %d ",v2[i],v2[i],key[v2[i]]);
        }
        if(v2.size()>1)    printf("%05d\n%05d %d -1\n",v2[v2.size()-1],v2[v2.size()-1],key[v2[v2.size()-1]]);
        else    cout<<"-1";
    }
    return 0;
}
